package com.example.system.class23;

/**
 * @Date 2022/8/24
 * @Author Jonathan
 */
public class Code02_MinCoinsNoLimit {
    public static void main(String[] args) {
        int[] coins = new int[]{5, 2, 1};
        System.out.printf("最少需要硬币数量: %d\n", minCoins(coins, 10));
    }

    public static int minCoins(int[] arr, int aim) {
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            // 已经没钱了 现在需要搞定的钱是0元 因此是需要0张
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        } else {
            int ans = Integer.MAX_VALUE;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                int next = process(arr, index + 1, rest - zhang * arr[index]);
                // 说明是0元0张的时候的返回值
                if (next != Integer.MAX_VALUE) {
                    ans = Math.min(ans, next + zhang);
                }
            }
            return ans;
        }
    }
}
